package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 110. 平衡二叉树
 * https://leetcode.cn/problems/balanced-binary-tree/description/
 */
public class LC110_BalancedBinaryTree {
    public static void main(String[] args) {

    }

    @XOptimal
    static
    class Solution {
        public boolean isBalanced(TreeNode root) {
            return getDepth(root) != -1;
        }

        private int getDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int leftDepth = getDepth(root.left);
            if (leftDepth == -1 ) {
                return -1;
            }
            int rightDepth = getDepth(root.right);
            if (rightDepth == -1 || Math.abs(leftDepth - rightDepth) > 1) {
                return -1;
            }
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}
